//顺序串
#ifndef __SEQUENTIALSTRING__HPP
#define __SEQUENTIALSTRING__HPP

#include"VirtualString.hpp"

namespace NgSiuKei {

#define KMP

class SequentialString: public VirtualString {
    public:
    SequentialString(void);
    ~SequentialString(void);

    public:
    //清空
    void clear(void);
    //使自身内容等于目标字符串
    void assign(const char * const str);
    //比较大小：self<str返回-1；self=str返回0；self>str返回S1
    int compare(const VirtualString *str) const;
    //拼接
    void concat(const VirtualString *str);
    //获取指定下标（index）开始的指定长度（len）的子串
    VirtualString *getSubstring(const U_L_L index, const U_L_L len) const;
    //获取子串在下标index后出现的位置，否则会抛出异常：EXCEPTION_CAN_NOT_FIND
    U_L_L getIndex(const VirtualString *str, const U_L_L index) const;
    //用str2替换字符串中所有与str1相等的子串
    void replace(const VirtualString *str1, const VirtualString *str2);
    //在指定下标处插入字符串
    void insert(const VirtualString *str1, const U_L_L index);
    //在指定下标处删除指定长度的子串
    void remove(const U_L_L index, const U_L_L len);
    //字符串本体
    const char * const getString(void) const;
    //打印
    void print(void) const;

    private:
    char *str;
};

SequentialString::SequentialString(void): VirtualString() {
    this->str = nullptr;
}

SequentialString::~SequentialString(void) {
    this->clear();
}

void SequentialString::clear(void) {
    this->len = 0;
    if(nullptr != this->str) {
        delete this->str;
        this->str = nullptr;
    }
}

void SequentialString::assign(const char * const str) {
    if(!this->isEmpty()) {
        this->clear();
    }
    
    //获取字符串长度
    U_L_L len = 0;
    for(U_L_L i=0; '\0' != str[i]; ++i) {
        len++;
    }
    
    this->str = new char[len+1];
    for(U_L_L i=0; i<len; ++i) {
        this->str[i] = str[i];
    }
    this->str[len] = '\0';
    this->len = len;
}

int SequentialString::compare(const VirtualString *str) const {
    char charA, charB;
    const char * const charStr = str->getString();
    const U_L_L len = str->getLen();
    const U_L_L minLen = ((this->len<len)?(this->len):(len));
    for(U_L_L i=0; i<minLen; ++i) {
        charA = this->str[i];
        charB = charStr[i];
        if(charA < charB) {
            return -1;
        }
        else if(charA > charB) {
            return 1;
        }
    }
    if(this->len == len) {
        return 0;
    }
    else if(this->len < len) {
        return -1;
    }
    else {
        return 1;
    }
}

void SequentialString::concat(const VirtualString *str) {
    const U_L_L len = str->getLen();
    const U_L_L newLen = this->len + len;
    const char * const charStr = str->getString();
    char *newStr = new char[newLen+1];
    U_L_L i;
    for(i=0; i<this->len; ++i) {
        newStr[i] = this->str[i];
    }
    for(i=0; i<len; ++i) {
        newStr[this->len+i] = charStr[i];
    }
    newStr[newLen] = '\0';
    this->clear();
    this->len = newLen;
    this->str = newStr;
}

VirtualString *SequentialString::getSubstring(const U_L_L index, const U_L_L len) const {
    if(index >= this->len) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }
    if(index+len-1 >= this->len) {
        return nullptr;
    }

    //提取子串
    char *newCharStr = new char[len+1];
    for(U_L_L i=0; i<len; ++i) {
        newCharStr[i] = this->str[index+i];
    }
    newCharStr[len] = '\0';

    //生成对象
    SequentialString *newStr = new SequentialString;
    newStr->assign(newCharStr);

    return newStr;
}

U_L_L SequentialString::getIndex(const VirtualString *str, const U_L_L index) const {
    if(index >= this->len || index+str->getLen() > this->len) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    const U_L_L len = str->getLen();
    const char * const charStr = str->getString();

#ifndef KMP
    //使用朴素匹配
    for(U_L_L tempIndex=index; tempIndex<=this->len-len; ++tempIndex) {
        for(U_L_L i=0; i<len; ++i) {
            if(this->str[tempIndex+i] != charStr[i]) {
                break;
            }
            else if(len-1 == i) {
                return tempIndex;
            }
        }
    }

#else
    //使用KMP模式匹配

    //先计算next数组
    unsigned int next[len];
    next[0] = 0;
    U_L_L preLen = 0;//前缀长度
    U_L_L i = 1;
    while(i<len) {
        if(charStr[i] == charStr[preLen]) {
            preLen++;
            next[i] = preLen;
            i++;
        }
        else {
            if(0 == preLen) {
                next[i] = 0;
                i++;
            }
            else {
                preLen = next[preLen-1];
            }
        }
    }

    //再遍历查找子串下标
    U_L_L j=0;//用于遍历子串的下标
    i=index;
    while(i<this->len) {
        if(this->str[i] == charStr[j]) {
            if(len-1 == j) {
                return i-j;
            }
            i++;
            j++;
        }
        else if(j>0) {
            j = next[j-1];
        }
        else {
            i++;
        }
    }

#endif

    throw EXCEPTION_CAN_NOT_FIND;
}

void SequentialString::replace(const VirtualString *str1, const VirtualString *str2) {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(nullptr == str1 || nullptr == str2) {
        throw EXCEPTION_NULL_POINTER;
    }
    if(str1->isEmpty()) {
        throw EXCEPTION_NULL_POINTER;
    }

    const U_L_L len1 = str1->getLen();
    const U_L_L len2 = str2->getLen();
    const char * const charStr1 = str1->getString();
    const char * const charStr2 = str2->getString();

    /*
    原来可以用getIndex、insert、remove三个函数就能很方便地实现功能，但是这样会有大量内存分配、释放操作
    所以我不干
    我要使用getIndex获取所有str1子串的位置，然后在一个新的内存空间内生成新的字符串*/

    U_L_L arrayIndex[this->len/len1];//可替换子串数量最多为总长度/子串长度，如：“aaaaa”最多可以替换2次“aa”，即使“aaaaa”里有4个“aa”
    U_L_L num = 0;//str1子串的数量

    try {//这里利用getIndex找不到子串时会抛出异常的特性退出循环
        U_L_L currentIndex = 0;
        while(true) {//获取所有str1的位置
            currentIndex = this->getIndex(str1, currentIndex);
            arrayIndex[num] = currentIndex;
            num++;
            currentIndex += len1;//当前子串所在区间可以跳过
        }
    }
    catch(Exception &e) {
        if(num > 0) {//统计完成了，开干
            U_L_L newLen = this->len+num*(len2-len1);
            char *newStr = new char[newLen+1];

            U_L_L j = 0;//遍历旧字符串用到的下标
            U_L_L k = 0;
            for(U_L_L i=0; i<newLen; ++i) {
                if(j == arrayIndex[k]) {//需要替换的位置
                    for(U_L_L l=0; l<len2; ++l, ++i) {
                        newStr[i] = charStr2[l];
                    }
                    j += len1;
                    k++;
                    i--;//上边设置新子串时最后一次循环++i与外侧循环++i冲突
                    continue;
                }
                newStr[i] = this->str[j];
                j++;
            }
            newStr[newLen] = '\0';

            this->clear();
            this->len = newLen;
            this->str = newStr;
        }
    }
}

void SequentialString::insert(const VirtualString *str, const U_L_L index) {
    if(index > this->len) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    const char * const newCharStr = str->getString();
    const U_L_L len = str->getLen();
    const U_L_L newLen = this->len+len;
    char *newStr = new char[newLen+1];
    
    U_L_L i;
    for(i=0; i<index; ++i) {
        newStr[i] = this->str[i];
    }
    for(i=0; i<len; ++i) {
        newStr[index+i] = newCharStr[i];
    }
    for(i=index; i<this->len; ++i) {
        newStr[i+len] = this->str[i];
    }
    newStr[newLen] = '\0';

    this->clear();
    this->len = newLen;
    this->str = newStr;
}

void SequentialString::remove(const U_L_L index, const U_L_L len) {
    if(index >= this->len || index+len-1 >= this->len) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    if(0 == len) {
        return;
    }

    //生成新字符串
    const U_L_L newLen = this->len-len;
    char *newCharStr = new char[newLen+1];
    for(U_L_L i=0; i<newLen; ++i) {
        if(i<index) {
            newCharStr[i] = this->str[i];
        }
        else {
            newCharStr[i] = this->str[i+len];
        }
    }
    newCharStr[newLen] = '\0';

    //重新设置字符串
    this->clear();
    this->len = newLen;
    this->str = newCharStr;
    //用成员函数assign更方便，但是实际运行上多了很多步骤
}

const char * const SequentialString::getString(void) const {
    return this->str;
}

void SequentialString::print(void) const {
    cout << this->str << endl;
}

}

#endif